The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for mining relevant approximate subgraphs from multigraphs.
A graph is an abstract data type that is meant to implement the graph and directed graph concepts from mathematics. A graph data structure consists of a finite (and possibly mutable) set of nodes or vertices, together with a set of ordered pairs of these nodes (or, in some cases, a set of unordered pairs). These pairs are known as edges or arcs. As in mathematics, an edge (x,y) is said to point or go from x to y. The nodes may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.). A directed graph (or digraph) is a graph, or set of nodes connected by edges, where the edges have a direction associated with them.
A multigraph is a graph that is permitted to have multiple edges (also called parallel edges), i.e., multiple edges that have the same end nodes. Thus two vertices may be connected by more than one edge. There are two distinct notions of multiple edges:
Edges without own identity: The identity of an edge is defined solely by the two nodes it connects. In this case, the term “multiple edges” means that the same edge can occur several times between these two nodes; and,
Edges with own identity: Edges are primitive entities just like nodes. When multiple edges connect two nodes, these are different edges.